package s12_经典算法.a4_贪心算法;

import java.util.*;

/**
 * Created by 西瓜瓜
 * Date :2022/2/27
 * Description :
 * Version :1.0
 *
 * 贪心算法
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {
        // 创建广播电台
        Map<String, List<String>> broadcasts = new HashMap<>();
        broadcasts.put("K1", Arrays.asList("北京","上海","天津"));
        broadcasts.put("K2", Arrays.asList("广州","北京","深圳"));
        broadcasts.put("K3", Arrays.asList("成都","上海","杭州"));
        broadcasts.put("K4", Arrays.asList("上海","天津"));
        broadcasts.put("K5", Arrays.asList("杭州","大连"));

        // 创建所有地区
        Set<String> allAreas = new HashSet<>();
        broadcasts.values().forEach(allAreas::addAll);

        // 创建存放电台的集合
        List<String> selects = new ArrayList<>();

        // 临时集合，在遍历过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> tempSet = new HashSet<>();

        // 创建清除电台的集合
        List<String> cleanSet = new ArrayList<>();

        // 标记一次遍历过程中能够覆盖最多未覆盖地区对应的电台的key， 如果maxKey 不为空，则会加入到selects中
        while(!allAreas.isEmpty()) {
            String maxKey = null;
            for (Map.Entry<String, List<String>> entry : broadcasts.entrySet()) {
                tempSet.clear();
                String key = entry.getKey();
                List<String> value = entry.getValue();
                tempSet.addAll(value);
                // 求出tempSet和allAreas的交集，交集会赋给tempSet
                tempSet.retainAll(allAreas);
                // 如果当前集合包含的未覆盖地区的数量比maxKey指向的集合地区还多，就需要重置maxKey
                if(!tempSet.isEmpty() && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
                if(tempSet.isEmpty()) {
                    cleanSet.add(key);
                }
            }

            if(maxKey != null) {
                // 将maxKey加入到selects集合中
                selects.add(maxKey);
                broadcasts.get(maxKey).forEach(allAreas::remove);
                cleanSet.add(maxKey);
            }

            if(!cleanSet.isEmpty()) {
                cleanSet.forEach(broadcasts::remove);
                cleanSet.clear();
            }
        }

        System.out.println(selects);

    }
}
